package java_0220.leetcode;

public class NumJZ36_ConvertTree1 {
    /**
     * 传入一个以pRootOfTree为根的BST，就能转为双向链表，并返回链表头节点
     * 1.有序双向链表，有序：使用中序遍历达到
     * 2.双向链表：prev.next->cur,cur.prev->prev;cur.next->next,next.prev->cur
     * @param pRootOfTree
     * @return
     */
    public TreeNode Convert(TreeNode pRootOfTree) {
       if(pRootOfTree==null){
           return null;
       }
       //遍历链表左子树
       TreeNode leftHead=Convert(pRootOfTree.left);
       //处理根节点连接
        TreeNode leftTail=leftHead;
        while(leftTail!=null&&leftTail.right!=null){
            leftTail=leftTail.right;
        }
        if(leftTail!=null){
            leftTail.right=pRootOfTree;
            pRootOfTree.left=leftTail;
        }
        //右子树//右链表
        TreeNode rightHead=Convert(pRootOfTree.right);
        if(rightHead!=null){
            rightHead.left=pRootOfTree;
            pRootOfTree.right=rightHead;
        }
        return leftHead==null?pRootOfTree:leftHead;
    }
}
